package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.ShowUtil;

/**
 * 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
 * <p>
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 * <p>
 * 示例 1:
 * <p>
 * 输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出: [[1,5],[6,9]]
 * 示例 2:
 * <p>
 * 输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出: [[1,2],[3,10],[12,16]]
 * 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 */
public class code57_插入区间 {
    public static void main(String[] args) {
        int[][] iii = new code57_插入区间().insert(
                new int[][]{
                        {1,2}
                        },
                new int[]{
                        4,8
                }
        );
        ShowUtil.showArrarr(iii);
    }

    /**
     * 最快解法,使用双重二分查找,查找到对应位置的信息,然后进行比较,时间复杂度是O(n+log(n))
     * @param intervals
     * @param newInterval
     * @return
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length==0){
            return new int[][]{
                    {newInterval[0],newInterval[1]}
            };
        }
        if(newInterval.length==0){
            return intervals;
        }
        int[] index = find(intervals, newInterval[0], newInterval[1]);
        int[][] newRes;
        if (index[0] == -1 && index[1] == -1) {
            newRes = new int[intervals.length + 1][2];
            newRes[0][0] = newInterval[0];
            newRes[0][1] = newInterval[1];
            for (int a = 0; a < intervals.length; a++) {
                newRes[a + 1][0] = intervals[a][0];
                newRes[a + 1][1] = intervals[a][1];
            }
        } else if (index[0] == intervals.length && index[1] == intervals.length) {
            newRes = new int[intervals.length + 1][2];
            for (int a = 0; a < intervals.length; a++) {
                newRes[a][0] = intervals[a][0];
                newRes[a][1] = intervals[a][1];
            }
            newRes[intervals.length][0] = newInterval[0];
            newRes[intervals.length][1] = newInterval[1];
        } else {
            if (newInterval[0] > intervals[index[0]][0]) {
                newInterval[0] = intervals[index[0]][0];
            }
            if (newInterval[1] < intervals[index[1]][1]) {
                newInterval[1] = intervals[index[1]][1];
            }
            newRes = new int[intervals.length - (index[1] - index[0])][2];
            int i = 0;
            while (i < index[0]) {
                newRes[i][0] = intervals[i][0];
                newRes[i][1] = intervals[i][1];
                i++;
            }
            newRes[i][0] = newInterval[0];
            newRes[i][1] = newInterval[1];
            i++;
            int j = index[1] + 1;
            while (j < intervals.length) {
                newRes[i][0] = intervals[j][0];
                newRes[i][1] = intervals[j][1];
                i++;
                j++;
            }
        }
        return newRes;
    }

    private int[] find(int[][] intervals, int left, int right) {
        int[] res = new int[2];
        if (right < intervals[0][0]) {
            res[0] = -1;
            res[1] = -1;
        } else if (left > intervals[intervals.length - 1][1]) {
            res[0] = intervals.length;
            res[1] = intervals.length;
        } else {
            res[0] = find(intervals, left, false);
            res[1] = find(intervals, right, true);
        }
        return res;
    }

    private int find(int[][] intervals, int item, boolean isRight) {
        int start = 0;
        int end = intervals.length - 1;
        int midle;
        while (start <= end) {
            midle = (end + start) >> 1;
            if (intervals[midle][0] <= item && intervals[midle][1] >= item) {
                return midle;
            } else if (intervals[midle][0] > item) {
                end = midle - 1;
            } else if (intervals[midle][1] < item) {
                start = midle + 1;
            }
        }
        if (isRight) {
            if (end >= intervals.length) {
                return intervals.length - 1;
            } else if (item < intervals[end][0]) {
                return end - 1;
            } else {
                return end;
            }
        } else {
            if (start < 0) {
                return 0;
            } else if (item > intervals[start][1]) {
                return start + 1;
            } else {
                return start;
            }
        }
    }
}
